public class Code1 {
    // 最长递增子序列的个数

    public int findNumberOfLIS(int[] nums) {
        // 创建 dp 表
        // 初始化
        // 填表
        // 返回值

        // 首先，还是简单粗暴地上来先定义出一个 dp 表
        // dp[i] 表示：以 i 位置元素结尾的所有子序列中，最长递增的子序列个数
        // 很显然，上面这种粗暴的方式是行不通的，我们甚至子序列的长度都不知道，何谈最长
        // 所以这里需要两个表来分别记录 最长子序列长度、最长子序列个数
        int n = nums.length;
        int[] len = new int[n];     // len[i] 表示：以 i 位置为结尾的元素中，最长递增子序列的 “长度”
        int[] count = new int[n];   // count[i] 表示：以 i 位置为结尾的元素中，最长递增子序列的 “个数”

        // 进行初始化操作，这里我们将两个数组中的值全部先初始化为 1
        for(int i = 0; i < n; i++){
            len[i] = count[i] = 1;
        }
        int retlen = 1;
        int retcount = 1;
        for(int i = 1; i < n; i++){
            for(int j = 0; j < i; j++){
                // 已知，这里是一个严格递增子序列
                if(nums[j] < nums[i]){
                    // 此时判断，当 j 的子序列长度等于 i 的子序列长度时，统计个数的 count 表增加
                    if(len[j] + 1 == len[i]){
                        count[i] += count[j];     // 当 j 的子序列长度小于 i 子序列时，不多做考虑
                    }else if(len[j] + 1 > len[i]){
                        // j 的 “长度” 大于 i ，此时需要重新计数
                        // 首先重置当前的长度
                        len[i] = len[j] + 1;
                        // 这里重新计数不能将数字设置为 1
                        // 因为这里是从 j 为结尾来计算的长度，所以这里需要重置为 j 位置时的 递增子序列“个数”
                        count[i] = count[j];
                    }
                }
            }
            // 同样的通过一个小贪心算法将长度和最大个数进行获取
            if(retlen == len[i]){
                retcount += count[i];
                // 这里获取的是最大长度下所对应的最多“个数”
            }else if(retlen < len[i]){
                retlen = len[i];
                retcount = count[i];
            }
        }
        return retcount;
    }
}
